\documentclass [11pt]{article}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{epsfig} 
\usepackage{enumerate}
\usepackage{xspace}

   \textwidth      15cm
   \textheight     23cm
   \oddsidemargin 0.5cm
   \topmargin    -0.5cm
   \evensidemargin\oddsidemargin

 \newcommand{\nop}[1]{}


   \pagestyle{plain}
   \bibliographystyle{plain}


\title{Formale Methoden der Informatik \\
Block 1: Computability and Complexity }
\author{
Thomas Prevedel, 0627595\\
Michael Sobotka, 0826407\\
Alexander Tomsu, 0803543
}
\date{SS 2012}



  \newtheorem{theorem}{Theorem}
  \newtheorem{lemma}[theorem]{Lemma}
  \newtheorem{corollary}[theorem]{Corollary}
  \newtheorem{proposition}[theorem]{Proposition}
  \newtheorem{conjecture}[theorem]{Conjecture}
  \newtheorem{definition}[theorem]{Definition}
  \newtheorem{example}[theorem]{Example}
  \newtheorem{remark}[theorem]{Remark}
  \newtheorem{exercise}[theorem]{Exercise}

  \newcommand{\ra}{\rightarrow}
  \newcommand{\Ra}{\Rightarrow}
  \newcommand{\La}{\Leftarrow}
  \newcommand{\la}{\leftarrow}
  \newcommand{\LR}{\Leftrightarrow}

  \renewcommand{\phi}{\varphi}
  \renewcommand{\theta}{\vartheta}


\newcommand{\ccfont}[1]{\protect\mathsf{#1}}
\newcommand{\NP}{\ccfont{NP}}

\newcommand{\NN}{\textbf{N}}
\newcommand{\IN}{\textbf{Z}}
\newcommand{\bigO}{\mathrm{O}}
\newcommand{\bigOmega}{\Omega}
\newcommand{\bigTheta}{\Theta}
\newcommand{\REACHABILITY}{\mbox{\bf REACHABILITY}}
\newcommand{\MAXFLOW}{\mbox{\bf MAX FLOW}}
\newcommand{\MAXFLOWD}{\mbox{\bf MAX FLOW(D)}}
\newcommand{\MAXFLOWSUB}{\mbox{\bf MAX FLOW SUBOPTIMAL}}
\newcommand{\MATCHING}{\mbox{\bf BIPARTITE MATCHING}}
\newcommand{\TSP}{\mbox{\bf TSP}}
\newcommand{\TSPD}{\mbox{\bf TSP(D)}}

\newcommand{\ThreeCol}{\mbox{\bf 3-COLORABILITY}}
\newcommand{\TwoCol}{\mbox{\bf 2-COLORABILITY}}
\newcommand{\kCol}{\mbox{\bf k-COLORABILITY}}
\newcommand{\HamPath}{\mbox{\bf HAMILTON-PATH}}
\newcommand{\HamCycle}{\mbox{\bf HAMILTON-CYCLE}}

\newcommand{\ONESAT}{\mbox{\bf 1-IN-3-SAT}}
\newcommand{\MONONESAT}{\mbox{\bf MONOTONE 1-IN-3-SAT}}
\newcommand{\kSAT}{\mbox{\bf k-SAT}}
\newcommand{\NAESAT}{\mbox{\bf NAESAT}}
\newcommand{\CLIQUE}{\textbf{CLIQUE}\xspace} 
\newcommand{\VC}{\textbf{VERTEX COVER}\xspace}



\renewcommand{\labelenumi}{(\alph{enumi})}

%%% useful macros for Turing machines:
\newcommand{\blank}{\sqcup}
\newcommand{\ssym}{\triangleright}
\newcommand{\esym}{\triangleleft}
\newcommand{\halt}{\mbox{h}}
\newcommand{\yess}{\mbox{``yes''}}
\newcommand{\nos}{\mbox{``no''}}
\newcommand{\lmove}{\leftarrow}
\newcommand{\rmove}{\rightarrow}
\newcommand{\stay}{-}
\newcommand{\diverge}{\nearrow}
\newcommand{\yields}[1]{\stackrel{#1}{\rightarrow}}

\newcommand{\HALTING}{\mbox{\bf HALTING}}

\newcommand{\true}{{\it true}}
\newcommand{\false}{{\it false}}


\newcommand{\samplesolution}[1]{\noindent {\bf Sample solution.}  #1}
\newcommand{\solution}[1]{\noindent {\bf Solution.}  #1}


\newcommand\rect[1]{
 \begin{picture}(-6,5)
\put(-6,0){\line(1,0){436}}
\put(-6,0){\line(0,-1){#1}}
\put(-6,-#1){\line(1,0){436}}
\put(430,0){\line(0,-1){#1}}
 \end{picture}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}


\setlength{\parindent}{0pt} % deactivates the indent
\setlength{\parskip}{1ex}


\maketitle


\begin{exercise}
  Consider the problem \textbf{PROCEDURE NEG-ASSIGNMENT}, which is defined
  as follows:

  \begin{center}
    \fbox{
      \begin{minipage}[c]{.9\linewidth}
        \textbf{PROCEDURE NEG-ASSIGNMENT}

        \medskip INSTANCE: A triple $(\Pi,I, k)$, where (i) $\Pi$ is a
        program that takes one string as input and outputs true or false, (ii) $I$ is a
        string, and (iii) $k$ is an integer variable used in program $\Pi$.     \\
        QUESTION: Does variable $k$ ever get assigned a negative value when the program $\Pi$ is executed with input $I$?

        
      \end{minipage}
    }
  \end{center}
  Prove that \textbf{NEG-ASSIGNMENT} is undecidable. Prove the undecidability
  by providing a reduction from the \textbf{HALTING} problem to
  \textbf{NEG-ASSIGNMENT}, and arguing that your reduction is correct.
\end{exercise}


\textbf{Solution}

Let ($\Pi$, \textit{I}) be an arbitrary instance of \textbf{HALTING}. We build an instance ($\Pi$', \textit{I}', \textit{k}) of \textbf{NEG-ASSIGNMENT} by setting \textit{I}' = \textit{I}, letting \textit{k} be an arbitrary integer number not occurring in $\Pi$, and constructing $\Pi'$ as follows:

\rect{100}

\textbf{Boolean} $\Pi'$ (\textbf{String S}) \{\\
\indent \quad \textbf{Integer} k; // define an integer number with name \textit{k}\\
\indent \quad \textbf{call} $\Pi$(S);\\
\indent \quad k = -3;\\
\indent \quad \textbf{return} true;\\
\}
\\
\\
In other words, for an instance x = $(\Pi,I)$, the instance R(x) resulting from the reduction is ($\Pi'$, \textit{I}', \textit{k}).

To prove the correctness of the reduction we have to show: ($\Pi$, \textit{I}) is a positive instance of \textbf{HALTING} $\Leftrightarrow$ ($\Pi'$, \textit{I}', \textit{k}) is a positive instance of \textbf{NEG-ASSIGNMENT}.

"$\Rightarrow$" Assume $(\Pi,I)$ is a positive instance of \textbf{HALTING}, i.e. $\Pi$ terminates on \textit{I}. Then the call of $\Pi(S)$ in program $\Pi'$ terminates on input \textit{I}' because S = \textit{I}' = \textit{I} by the problem reduction. Hence, the negative variable assignment k = -3 in $\Pi'$ is executed. It follows that ($\Pi'$, \textit{I}', \textit{k}) is a positive instance of \textbf{NEG-ASSIGNMENT}.

"$\Leftarrow$" Assume ($\Pi'$, \textit{I}', \textit{k}) is a positive instance of \textbf{NEG-ASSIGNMENT}, i.e. $\Pi'$ sets the variable \textit{k} to any negative integer-value when called with input \textit{I}'. Observe that the first statement which assigns \textit{k} a negative integer value is after the call $\Pi$(\textit{I}'). Sine \textit{I}' = \textit{I}, we have that $\Pi$ terminates on \textit{I}, i.e. that ($\Pi$, \textit{I}) is a positive instance of \textbf{HALTING}.

\newpage


\begin{exercise}
  Prove that the problem \textbf{NEG-ASSIGNMENT} from Exercise 1 is semi-decidable. 
To this end, provide a semi-decision procedure and justify your solution. Additionally,  show that the co-problem of \textbf{NEG-ASSIGNMENT} is not semi-decidable.
\end{exercise}


\solution{

\textbf{1. Proof that NEG-ASSIGNMENT is semi-decidable}

To show that \textbf{NEG-ASSIGNMENT} is semi-decidable, we write an interpreter $\Pi'$ that takes as input $(\Pi, I, k)$ and simulates the run of $\Pi$ on $I$.


\begin{itemize}
\item If the simulation reaches the point where a negative value is assigned to $k$, then $\Pi'$ returns $true$.
\item If the simulation ends without ever assigning a negative value to $k$, then $\Pi'$ returns $false$.
\end{itemize}

We argue that such an interpreter $\Pi'$ is a semi-decision procedure for \textbf{NEG-ASSIGNMENT}. We distinguish the following cases:

\begin{itemize}
\item Case 1: Suppose that $(\Pi, I, k)$ is a positive instance, i.e., in $\Pi$ on the string $I$ as input, $k$ gets assigned a negative value. Then the simulation in $\Pi'$ will encounter an assignment where k gets a negative value and return $true$ by the construction of $\Pi'$.
\item Case 2.1: Suppose that $(\Pi, I, k)$ is a negative instance and that $\Pi$ halts on input $I$. Then $\Pi$ halts without ever assigning $k$ a negative value. Hence, the simulation in $\Pi'$ will detect that $k$ never got assigned a negative value on input $I$. Thus, $\Pi'$ returns $false$ by the construction of $\Pi'$.
\item Case 2.2: Suppose that $(\Pi, I, k)$ is a negative instance and that $\Pi$ does not halt on input $I$. Then the simulation of this computation of $\Pi$ on $I$ by the interpreter $\Pi'$ will not terminate either. Hence, $\Pi'$ will run forever on the negative instance $(\Pi, I, k)$, which is a correct behavior for a semi-decision procedure.
\end{itemize}

\textbf{2. Proof that the co-problem of NEG-ASSIGNMENT is not semi-decidable}

Since \textbf{NEG-ASSIGNMENT} is a decision problem, we can show that the co-problem of \textbf{NEG-ASSIGNMENT} (i.e. \textit{"Does variable k \textbf{never} get assigned a negative value when the program $\Pi$ is executed with input I?"})  is not semi-decidable without going into details about the problem itself.

We first show that, (1) if $P$ is a decision problem, $\bar{P}$ is the complement of $P$, and both $P$ and $\bar{P}$ are semi-decidable, then $P$ is decidable.

After that we can show that, (2) if $P$ is undecidable and also semi-decidable (which holds for \textbf{NEG-ASSIGNMENT}, then the complement $\bar{P}$ of $P$ is not  semi-decidable.

Proof of (1): Since $P$ is semi-decidable, there is a program $\Pi_P$ that terminates and returns $true$ on all positive instances of $\Pi$. Since $\bar{P}$ is semi-decidable, there is a program $\Pi_{\bar{P}}$ that terminates and returns $true$ on all positive instances of $\bar{P}$, or equivalently, on all negative instances of $P$. We now define $\Pi'$ that runs $\Pi_P$ and $\Pi_{\bar{P}}$ in parallel, and outputs the corresponding result when one of the two programs terminates (termination of one triggers termination of the other).

Proof of (2): We prove by contradiction. Suppose $\bar{P}$ (co-problem of \textbf{NEG-ASSIGNMENT}) is semi-decidable. Since $P$ and $\bar{P}$ are both semi-decidable, then $P$ is decidable, as we have shown in (1). This contradicts the assumption that $P$ is undecidable. We can infer that the complement of \textbf{NEG-ASSIGNMENT} is not semi-decidable.

}

\newpage

\begin{exercise}
  Give a formal proof that \textbf{SUBSET SUM} is in $\NP$, i.e.\, define a
  certificate relation and discuss that it is polynomially balanced and
  polynomial-time decidable.
  
   \smallskip
    
  \noindent In the \textbf{SUBSET SUM} problem we are given a finite set of integer numbers $S=\{a_1, a_2, \ldots, a_n\}$ and an integer number $t$. We ask whether there is a subset $S'\subseteq S$ whose elements sum is equal to $t$?
  
\end{exercise}


\solution{

To prove that \textbf{SUBSET SUM} $\in \NP$ we have to define a polynomially balanced and polynomially decidable certificate relation for \textbf{SUBSET SUM}. Simply let

\vspace{2ex}

\centerline { $ R = \{ ((S, t), S') \:  | \: S'=\{b_1, ..., b_k \}, S'\subseteq S, \sum_{i=1}^{k} b_i = t \} $ }

\vspace{2ex}

R is a certificate relation by construction: (S, t) is a positive instance of \textbf{SUBSET SUM} $ \Leftrightarrow $ there exists a subset $ S'\subseteq S $ whose elements sum is equal to t 
$ \Leftrightarrow ((S, t), S') \in R $

R is \textbf{polynomially decidable} because given a pair (S, t) and S' (where $|S| = n$ and $|S'| = k$), you can decide in polynomial time whether S' is a subset of S (by searching each element of S' in S which takes $\bigO (n^2)$), and summing up all k elements of S' and comparing it to t clearly can be computed in linear time.

Since $ S'\subseteq S$, R is \textbf{polynomially balanced} because $ |S'| \leq |S|^k$ for some fixed $k \geq 1$. This always holds even for k = 1: The number of elements of the solution S' is at most as large as the number of elements of the problem instance (S, t). 



}

\newpage

\begin{exercise}
  \label{ex:partition}
  Formally prove that \textbf{PARTITION} is $\NP$-complete. For this you may use
  the fact that \textbf{SUBSET SUM} is $\NP$-complete.   
  
  \smallskip
  \noindent In the \textbf{PARTITION} problem we are given a finite set of integers $S=\{a_1, a_2, \ldots, a_n\}$. We ask whether the set $S$ can be partitioned into two sets $S_1, S_2$ such that the sum of the numbers in $S1$ equals the sum of the numbers in $S_2$? 
  
\end{exercise}

\textbf{Solution}

We show that \textbf{PARTITION} is NP-complete by providing a reduction from \textbf{SUBSET SUM} to \textbf{PARTITION} and showing that \textbf{PARTITION} is indeed a member of the class NP.

\textbf{1. NP-Membership}

We define the certificate relation R:

\vspace{2ex}

\centerline { $ R = \{ (L, (l_1,l_2)) \:  | \: l_1 \cup l_2 = L, l_1 \cap l_2 = \emptyset, \sum{l_1} = \sum{l_2} \} $ }

\vspace{2ex}

R is a certificate relation by construction. A list of elements L is a positive instance of \textbf{PARTITION} $ \Leftrightarrow $ there exists a partition of L into the sublists $l_1$ and $l_2$ so that the sum of their elements is equal $ \Leftrightarrow (L, (l_1,l_2)) \in R $

R is \textbf{polynomially balanced} because $ |l_1| + |l_2| = |L| $. The number of elements for the solution is equal to the number of elements of the problem instance L.

R is \textbf{polynomially decidable} because summing up k elements can be clearly computed in linear time, which is equally true for checking whether an element is part of a list.

\textbf{2. Reduction}

Let $ I_s = (L,t) $ be an arbitrary instance of \textbf{SUBSET SUM} with a given list of integers $ L = [a_1, a_2, ..., a_n] $ and a given sum t.

We construct the instance $I_p$ of \textbf{PARTITION} as follows: 

\vspace{2ex}

\centerline{ $I_p = (L')$ where $L' = L \cup \{e\} \: , \: e = (\sum{L}) - 2t $ }

\vspace{2ex}

In other words: We modify L by adding one new element e to L. The computation of e is possible in polynomial time as it only involves summing up the elements of L.

Now we prove that this reduction is correct by showing that the following statement holds:

\vspace{2ex}

\centerline { $I_s = (L,t)$ is a positive instance of \textbf{SUBSET SUM} $\Leftrightarrow$ }
\centerline { $I_p = (L')$ is a positive instance of \textbf{PARTITION} }

\vspace{2ex}

\textbf{2.a Proof of correctness: Direction "$\Leftarrow$"}

If $I_p = (L')$ is a positive instance of \textbf{PARTITION}, there is a valid partition $L' = l_1 \cup l_2  $ of the modified list L' and we know that the sum of the elements of $l_1$ and $l_2$ must equal half the sum of L'. 

The sum of L' itself is: $\sum{L'} = \sum{L} + e = \sum{L} + (\sum{L}) - 2t = 2(\sum{L}) - 2t$

Thus, it holds that: $ \sum{l_1} = \sum{l_2} = \frac{\sum{L'}}{2} = (\sum{L}) - t$

Because we inserted the element e into the modified list L', we know that e must be contained in either $l_1$ or $l_2$.

Therefore, one of the two partitioned lists must have the form: $ l_i = [a_x, a_y, ..., a_z, e] $ .

Now we subtract e from the sum of $ l_i $.

\vspace{2ex}

\centerline{ $ \sum{[a_x, a_y, ..., a_z]} = \sum{l_i} - e = (\sum{L} - t) - (\sum{L} - 2t) = t $ }

\vspace{2ex}

We observe that in the partition $l_i$ there exists a list of elements $[a_x, a_y, ..., a_z]$ that sum up to the value t, which is exactly the desired solution to \textbf{SUBSET SUM}.

\textbf{2.b Proof of correctness: Direction "$\Rightarrow$"}

If $I_s = (L,t)$ is a positive instance of \textbf{SUBSET SUM}, there is a sublist $l_1 = [a_x, a_y, ..., a_z]$ where $\sum{l_i} = t$. This list $l_i$ together with e forms a partition, because $\sum({l_i \cup e)} = (\sum{L}) - t $, which is exactly half the sum of L'.


\newpage

\begin{exercise}
  \label{ex:frequency}
  Formally prove that \textbf{FREQUENCY ASSIGNMENT} is $\NP$-complete. For this you may use
  the fact that a similar problem used in lectures is $\NP$-complete.
      
    \smallskip
        
  \noindent In the \textbf{FREQUENCY ASSIGNMENT} problem we are given a set of transmitters $T=\{t_1, t_2, \ldots, t_n\}$,  $k$ frequencies, and the list of pairs of transmitters that interfer and therefore cannot use the same frequency. We ask whether there is an assignment of each transmitter to one of $k$ frequencies such that there is no interference between the transmitters. 
            
\end{exercise}

\solution{

We show that \textbf{FREQUENCY ASSIGNMENT} is NP-complete by providing a reduction from \textbf{k-COLORABILITY} to \textbf{FREQUENCY ASSIGNMENT} and showing that \textbf{FREQUENCY ASSIGNMENT} is a member of the class NP.

\textbf{1. NP-Membership}

Let $T=\{t_1,t_2,\ldots,t_n\}$ denote the set of transmitters, $F=\{f_1,f_2,\ldots,f_k\}$ the set of available frequencies, $I \subseteq T \times T$ the pairs of interfering transmitters and $A \subseteq T \times F$ the set of tuples: (transmitter $t_x$, assigned frequency $f_y$). 

We define the certificate relation R as follows:

\vspace{2ex}

\centerline { $ R = \{ ((T,F,I), A) \:  | \: |T|=|A|, \nexists \: a_i = (t_i,f), a_j = (t_j,f) \in A $ so that $ (t_i, t_j) \in I \} $ }

\vspace{2ex}

The 3-tuple (T,F,I) is a positive instance of \textbf{FREQUENCY ASSIGNMENT} $\Leftrightarrow$ A is a valid and complete assignment of frequencies to transmitters iff each transmitter gets assigned exactly one frequency and there are no pairs of interfering transmitters $t_i$ and $t_j$ in A $\Leftrightarrow ((T,F,I), A) \in R$ 

R is \textbf{polynomially balanced} because $ |A| + |T| = n $. Each transmitter occurs exactly once in the assignment.

R is \textbf{polynomially decidable}. To check the correctness of the assignment, it is sufficient to iterate through I (= set of interfering transmitters) once. For each pair $(t_i,t_j) \in I$ it must be checked whether they got a different frequency assigned. This can be done in quadratic time with 2 nested loops.

\textbf{2. Reduction}

Let $I_f = (T,F,I)$ be an arbitrary instance of \textbf{FREQUENCY ASSIGNMENT}. We construct the instance $I_c$ of \textbf{k-COLORABILITY} as follows:

\vspace{2ex}

\centerline { $I_c = (T, I, k)$ }

\vspace{2ex}

We use the transmitters as the nodes of the graph. Interfering transmitters are represented by an edge in the graph.

We prove the correctness of this reduction by proving that the following statement holds:

\vspace{2ex}

\centerline { $I_f = (T,F,I)$ is a positive instance of \textbf{FREQUENCY ASSIGNMENT} $\Leftrightarrow$ }
\centerline { $I_c = (T,I,k)$ is a positive instance of \textbf{k-COLORABILITY} }

\vspace{2ex}

\textbf{2.a Proof of correctness: Direction "$\Rightarrow$"}

Assume $I_f = (T,F,I)$ is a positive instance of \textbf{FREQUENCY ASSIGNMENT}. From this we know that there exists a valid frequency-assignment, so that no two interfering transmitters share the same frequency. If we just replace the word 'interfering' by the word 'connected', we can build a graph G = (T,I) where we directly use the set of interfering transmitters I as the edges. So, each $i = (t_1,t_2) \in I$ becomes an edge in our graph.

By this construction we know that if there is an edge between two nodes $t_i$ and $t_j$, they have a different assigned frequency, because otherwise they would not be connected. We can express this fact by coloring the nodes $t_i$ and $t_j$ with a different color.

Since we know that $I_f$ can be solved by using k different frequencies, our graph can also be colored with k different colors, as a color is just a synonym for a frequency.

\textbf{2.b Proof of correctness: Direction "$\Leftarrow$"}

If $I_c = (T,I,k)$ can be k-colored so that no two connected nodes have the same color, we can simply map every color to one of the k given frequencies in F. Now we know by the construction of the graph that no connected (=interfering) transmitters share the same frequency. Therefore, $I_f = (T,F,I)$ must be a positive instance of the frequency-assignment problem.

}


\newpage

\begin{exercise}
  \label{ex:CO-NP}
  Fomally prove that logical entailment is $co-\NP$-complete. The formal definition of entailment ( $\models$) is this: $\alpha \models \beta$ if and only if, in every truth assignment in which $\alpha$ is true, $\beta$ is also true.  
\end{exercise}


\textbf{Solution}

The proof consists of two parts:
\begin{itemize}
\item (A) showing that \textbf{CO-LOGICAL-ENTAILMENT} is in NP, and
\item (B) showing NP-hardness of \textbf{CO-LOGICAL-ENTAILMENT}, i.e. that for all problems \textit{P'} in NP, \textit{P'} is reducible to \textbf{CO-LOGICAL-ENTAILMENT}.
\end{itemize}

For the part (A), we define the relation

\indent \quad $R = \{(\alpha \not\models \beta, \mu) |$ formula $\alpha$ evaluates to true and formula $\beta$ evaluates to false under assignment $\mu \}$

We argue that $R$ is a certificate relation for \textbf{CO-LOGICAL-ENTAILMENT}. Indeed the following quivalences hold: $\alpha \not\models \beta$ is a positive instance of \textbf{CO-LOGICAL-ENTAILMENT} $\Leftrightarrow$ there exists at least one truth assignment in which $\alpha$ is true and $\beta$ is false $\Leftrightarrow$ $(\alpha \not\models \beta, \mu) \in R$.

$R$ is polynomially balanced because each assignment $\mu$ for the formulas $\alpha$ and $\beta$ can be represented as a subset of variables in $\alpha \not\models \beta$.

Finally $R$ is decidable in polynomial time because evaluating the Boolean circuits $C(\alpha)$ and $C(\beta)$ under $\mu$ takes only polynomial time (as seen in the lecture).

For the part (B), we reduce \textbf{CO-VALIDITY} to \textbf{CO-LOGICAL-ENTAILMENT}. Such a reduction suffices, because any problem \textit{P'} in NP can be reduced to \textbf{CO-LOGICAL-ENTAILMENT} by composing (i) a reduction from \textit{P'} to \textbf{CO-VALIDITY} (which exists because of co-NP-completeness of \textbf{VALIDITY}), and (ii) the reduction from \textbf{CO-VALIDITY} to \textbf{CO-LOGICAL-ENTAILMENT}.

Thus let $\phi$ be an arbitrary instance of \textbf{CO-VALIDITY}, i.e., $\phi$ is a propositional logic formula. We construct the instance $\not\models \phi$ of \textbf{CO-LOGICAL-ENTAILMENT}. This reduction is feasible in polynomial time. It remains to prove the correctness.

\begin{itemize}
\item "$\Rightarrow$" Assume $\phi$ is a positive instance of \textbf{CO-VALIDITY}, i.e. there exists a variable assignment $\mu$ so that $\phi$ evaluates to false. According to the definition of $\not\models$ the empty set is always true. Because $\alpha \not\models \beta$ only evaluates to true when there exists a variable assignment for which $\alpha$ is true and $\beta$ is false, and we have $\alpha = \{\}$, i.e. always evaluates to true, and $\phi = \beta$ it remains to show that there exists a variable assignment $\mu$ so that $\phi$ evaluates to false, which is exactly the definition of a positive instance of \textbf{CO-VALIDITY}. It follows that $\not\models \phi$ is a positive instance of \textbf{CO-LOGICAL-ENTAILMENT}.
\item "$\Leftarrow$" Assume $\alpha \not\models \beta$ is a positive instance of \textbf{CO-LOGICAL-ENTAILMENT}, i.e. there exists a variable assignment $\mu$ so that the formula $\alpha$ evaluates to true and the formula $\beta$ evaluates to false. By applying the \textbf{Deduction Theorem} of propositional logic entailment we can easily create an equal instance of \textbf{CO-LOGICAL-ENTAILMENT} to $\alpha \not\models \beta$ which looks exactly like: $\not\models \alpha \to \beta$. By setting $\phi = \alpha \to \beta$ the remaining construct $\not\models \phi$ means that there exists a variable assignment $\mu$ so that $\phi$ evaluates to false, which is exactly the definition of a positive instance of \textbf{CO-VALIDITY}. It follows that $\alpha \not\models \beta$ is a positive instance of \textbf{CO-VALIDITY}.
\end{itemize}

\newpage



\begin{exercise}
  \label{ex:Colors}
  It is well known that the \textbf{k-COLORABILITY} problem is $\NP$-complete for every $k \geq 3$. Recall that the instance of \textbf{k-COLORABILITY} is an undirected graph $G = (V, E)$. Suppose that we restrict this instance of \textbf{k-COLORABILITY} to trees. Can the restricted problem be solved with an algorithm that runs in polynomial time? If yes, provide such an algorithm. 
\end{exercise}


\solution{

Yes, there exists an algorithm which solves \textbf{k-COLORABILITY} for trees in polynomial time (for $k \geq 2$):\newline
The algorithm \textbf{colorTree} starts by coloring the root vertex of tree $ T = (V, E) $ and performs a pre-order traversal. Each vertex on the same level gets an assignment of the same color. Therefore vertices in T can always be colored with at least 2 different colors such that any two vertices $ i, j $ connected by an edge $ [i, j] \in E $ do not have the same color.\newline
If $k < 2$, a tree cannot be colored this way.

\textbf{We assume the following methods (implementable to run in log. time):}
\begin{itemize}
\item \textbf{root(T)} returns the root of tree T
\item \textbf{colorVertex(v, c)} assigns color c to vertex v
\item \textbf{switchColor(c)} returns the color 'BLACK' when c is 'WHITE' and vice versa (returns 'WHITE' when c is 'BLACK')
\item \textbf{children(v)} returns all children (direct descendants) from vertex v
\end{itemize}

\rect{250}

\textbf{Boolean} colorTree(Tree t, Integer k) \{\\
\indent \quad \textbf{if} (k $\leq$ 2) \textbf{then} \{\\
\indent \quad \quad Color c = 'BLACK';\\
\indent \quad \quad r = root(T);\\
\indent \quad \quad colorVertex(r, c);\\
\indent \quad \quad colorChildren(r, switchColor(c));\\
\indent \quad \quad \textbf{return true}\\
\indent \quad \}\\
\indent \quad \textbf{return false}\\
\}\\



colorChildren(Vertex v, Color c) \{\\
\indent \quad \textbf{foreach} child $\in$ children(v) \{\\
\indent \quad \quad colorVertex(child, c);\\
\indent \quad \quad colorChildren(child, switchColor(c));\\
\indent \quad \}\\
\}\\

Since each vertex is visited only once, the algorithm runs in linear time w.r.t. the size of V and therefore also in polynomial time.

}


\newpage

\begin{exercise}
  \label{ex:Nqueens}
  Provide a reduction of \textbf{N-Queens} problem to \textbf{SAT}. Give a proof sketch of the correctness of your reduction. Does this implies that the \textbf{N-Queens} is an $\NP$-complete problem? Argue your answer.  
  
  \smallskip 
  
\noindent In the \textbf{N-Queens} problem we are given $n$ queens and an $n \times n$ chessboard. We ask whether we can place these $n$ queens on the  chessboard such that no two queens attack each other. Two queens attack each other if they are placed in the same row, or in the same column, or in the same diagonal.    
       
   
\end{exercise}

\textbf{Solution}

We reduce the \textbf{N-Queens} problem to \textbf{SAT} as follows:

For each field on the chessboard a boolean variable $ f_{ij} $ is introduced, where i represents the row and j the column number of the field. The intended meaning of $ f_{ij} = true $ is that there is a queen positioned on this field.

We have to deal with 3 restrictions according to the rules of chess:
\begin{enumerate}[\quad 1]
	\item In each row there must not be more than one queen.
	\item In each column there must not be more than one queen.
	\item If a queen is placed on a field, it is not allowed to place another queen on a diagonally reachable field.
\end{enumerate}

The basic representation of the \textbf{N-Queens} problem as a boolean formula is:

\vspace{2ex}

\centerline{ $ (f_{11} \vee f_{12} \vee ... \vee f_{1n}) \wedge (f_{21} \vee f_{22} \vee ... \vee f_{2n}) \wedge ... \wedge (f_{n1} \vee f_{n2} \vee ... \vee f_{nn}) $ }

\vspace{2ex}

This formula basically states that there must be at least one queen in each row. Only then each of the clauses can evaluate to true.

Now we extend this basic formula by adding further formulas that represent the 3 restrictions listed above.

\vspace{2ex}

\centerline{ $ (f_{ij} \rightarrow \neg f_{ik}) \quad , \quad i \in \{1...n\}, k \in \{1...n\} \backslash j $ }

\vspace{2ex}

These formulas state that if there is a queen placed on field $ f_{ij} $ there must not be placed a queen on any of the fields on the same row. Thus, restriction 1 is met.

In the same way, we can express the restriction on the columns:

\vspace{2ex}

\centerline{ $ (f_{ij} \rightarrow \neg f_{kj}) \quad , \quad j \in \{1...n\}, k \in \{1...n\} \backslash i $ }

\vspace{2ex}

These formulas state that if there is a queen placed on field $ f_{ij} $ there must not be placed a queen on any of the fields on the same column. Therefore, restriction 2 is also met.

The formulation of restriction 3 looks a little more complicated:

\vspace{2ex}

\centerline{ $ (f_{ij} \rightarrow \neg f_{i \pm c, j \pm c}) \quad , \quad c \in \{1...n\}, \quad 0 < i \pm c \leq n , \quad 0 < j \pm c \leq n$ }

\vspace{2ex}

By adding a constant c to the column index j of a given field, we reach the field c steps to the right. If we subtract c from the column index j, we reach the field c steps to the left. Applied on the row index, we reach the fields c steps in vertical direction. The boundaries are there to ensure we do not move outside of the board.\\
These formulas satisfy restriction 3, stating that there must not be placed queens on the same diagonal.

Finally we conjunct all formulas, resulting in the input formula for \textbf{SAT}.

If this final formula can be satisfied, we know that there must be a solution to the \textbf{N-Queens} problem.

It does, however not imply that \textbf{N-Queens} is an NP-complete problem. From the reduction to \textbf{SAT} we can only deduct that \textbf{N-Queens} is not harder than \textbf{SAT}, but it could be easier.

\newpage

\begin{exercise}
  Consider the following problem:
  \begin{center}
    \fbox{
      \begin{minipage}[c]{.95\linewidth}
        \textbf{N-SORTED-ELEMENTS}

        \medskip

        INSTANCE: A non-empty list $L=(e_1,\ldots,e_n)$ of non-negative integers. \\
        QUESTION: Does the list $L$ contain a sub-list of $k$ consecutive sorted numbers in ascending order (from left to right)?
      \end{minipage}
    }
  \end{center}

  \medskip Argue that \textbf{N-SORTED-ELEMENTS} can be solved using only logarithmic
  space.
\end{exercise}

\textbf{Solution}

A problem \textbf{P} $\in$ L if there is a program such that for all instances \textit{I} of \textbf{P}, the program uses at most O($\log _2 \left( |I| \right)$) bits of read/write memory. To show that \textbf{N-SORTED-ELEMENTS} $\in$ L we will provide a procedure which solves the problem using only logarithmic space.\\

\textbf{We assume the following methods (implementable to run in log. space):}
\begin{itemize}
\item \textbf{root(L)} returns the root-node of the List L
\item \textbf{next(L, x)} returns the follower-node of a node x in the List L or nil if no such node exists
\item \textbf{labelling(L, x)} returns the Integer-label of a node x in the List L
\end{itemize}
\rect{200}\\
\textbf{Boolean} check(List L, Integer k)\{\\
\indent \quad \textbf{Integer} counter = 0;\\
\indent \quad previous = root(L);\\
\indent \quad actual = next(L, previous);\\
\indent \quad \textbf{while}(actual != nil) \{\\
\indent \quad \quad \textbf{if} labelling(L, previous) $\leq$ labelling(L, actual) \textbf{then} counter = counter + 1;\\
\indent \quad \quad \textbf{if} labelling(L, previous) $>$ labelling(L, actual) \textbf{then} counter = 0;\\
\indent \quad \quad \textbf{if} counter == k \textbf{then return true};\\
\indent \quad \quad previous = actual;\\
\indent \quad \quad actual = next(L, actual);\\
\indent \quad \}\\
\indent \quad \textbf{return false};\\
\}\\
\\
\\
\indent In the worst case the procedure above iterates exactly one time over the whole list using the pointers \textit{previous} and \textit{actual} which refer to the previous and the actual list elements. By increasing an counter the proceduree checks how many consecutive sorted numbers in ascending order (from left to right) exist and returns \textit{true} if this number equals the given integer number \textit{k}. If one list element with an integer-label with not ascending order is reached then the counter is set back to the value \textit{0} and begins to count again for the rest of the list. If no sub-list of \textit{k} consecutive sorted numbers in ascending order is found the procedure returns \textit{false}.\\

\textbf{The procedure above requires only logarithmic space in the size of the input because:}
\begin{itemize}
\item the two pointer variables \textit{previous} and \textit{actual} and the counter variable \textit{counter} each require only log \textit{m} bits of memory, where \textit{m} is the size of \textit{L}.
\item the number of pointers used in the procedure is constant, i.e. two.
\item the number of counters used in the procedure is constant, i.e. one.
\end{itemize}


\newpage

\begin{exercise}
  \label{ex:turing}

  Design a Turing machine that increments by one a value represented by a string of 0s and 1s.

\end{exercise}

We construct a Turing machine $M = (K, \Sigma, \delta, s)$ as follows:

\begin{itemize}
	\item $ K = \{s,a,b,c\} \cup \{\halt\} $
	\item $ \Sigma = \{0,1,\ssym,\blank\} $
	\item and the transition-function $ \delta $ as described below:
\end{itemize}
\begin{eqnarray*}
\delta (s,\ssym) &=& (s,\ssym,\rmove)\\
\delta (s,1) &=& (s,1,\rmove)\\
\delta (s,o) &=& (s,0,\rmove)\\
\delta (s,\blank) &=& (a,\blank,\lmove)\\
\delta (a,0) &=& (\halt,1,\stay)\\
\delta (a,1) &=& (a,0,\lmove)\\
\delta (a,\ssym) &=& (b,\ssym,\rmove)\\
\delta (b,0) &=& (c,1,\rmove)\\
\delta (c,0) &=& (c,0,\rmove)\\
\delta (c,\blank) &=& (\halt,0,\stay)\\
\end{eqnarray*}

\textbf{Description}:

In start-state s, the cursor moves to the right, no matter what symbol occurs and does not alter the input (lines 1, 2, 3).\\
Finally, the cursor must reach the end of the input (the first $\blank$-symbol), which is expressed in line 4.

At this point, the machine switches to state 'a' and moves one position to the left, positioning the cursor at the very last digit of the input number.\\
Now there are 2 possibilities:

\begin{enumerate}
	\item If the current symbol is 0, it can be simply overwritten by 1 and the computation is finished. The machine switches to the halting-state (line 5).
	\item If the current symbol is 1, it must be overwritten by 0 according to the rules of binary-addition. Further, the cursor moves one step to the left, since the carry-bit has to be processed (line 6).
\end{enumerate}

In the worst case, the input consists of only 1s, meaning that the carry-bit would have to be placed in front of the input.

Line 7 deals with this special case.

If the start-symbol $\ssym$ is reached again during the left-movement, the machine switches to a new state b and positions the cursor at the very first symbol of the input, which now must consist of only 0s.

The first 0 is overwritten by 1 (so the carry-bit is now processed).

The only thing left to do now is to add an additional 0 at the very end of the input because the machine just truncated the number of digits of the result by one.

Therefore the machine switches into another new state c. The cursor moves constantly to the right without altering the input.\\
At the very end, the $\blank$-symbol is reached, which is overwritten by the missing 0. The computation is finished and the machine halts (line 10).

\end{document}